
import java.util.ArrayList;
import java.util.Random;


public class Sort {

	/**
	 * Implement insertion sort.
	 * 
	 * It should be:
	 *  inplace
	 *  stable
	 *  
	 * Have a worst case running time of:
	 *  O(n^2)
	 *  
	 * And a best case running time of:
	 *  O(n)
	 * 
	 * @param arr
	 */
	public static <T extends Comparable<T>> void insertionsort(T[] arr) {
		int j;
		for (int i=1;i<arr.length;i++) {
			T check = arr[i];
			for (j=i;j>0;j--) {
				if (check.compareTo(arr[j-1])<0)
					arr[j] = arr[j-1];
				else {
					arr[j] = check;
					break;}
				if (j==1) 
					arr[0] = check;}
		}
	}



	/**
	 * Implement quick sort. 
	 * 
	 * Use the provided random object to select your pivots.
	 * For example if you need a pivot between a (inclusive)
	 * and b (exclusive) where b > a, use the following code:
	 * 
	 * int pivotIndex = r.nextInt(b - a) + a;
	 * 
	 * It should be:
	 *  inplace
	 *  
	 * Have a worst case running time of:
	 *  O(n^2)
	 *  
	 * And a best case running time of:
	 *  O(n log n)
	 * 
	 * @param arr
	 */
	public static <T extends Comparable<T>> void quicksort(T[] arr, Random r) {
		quicksort(arr,r,0,arr.length-1);
	}

	private static <T extends Comparable<T>> void quicksort(T[] arr, Random r, int n1, int n2) {
		if (n1 >= n2) return;
		int pivotIndex = r.nextInt(n2-n1)+n1;
		pivotIndex = partition(arr,n1,n2,pivotIndex);
		quicksort(arr,r,n1,pivotIndex-1);
		quicksort(arr,r,pivotIndex,n2);
	}

	private static <T extends Comparable<T>> int partition(T[]arr, int n1, int n2, int pivotIndex) {
		T pivot = arr[pivotIndex];
		while (n1<=n2) {
			while (pivot.compareTo(arr[n1])>0) n1++;
			while (pivot.compareTo(arr[n2])<0) n2--;
			if (n1<=n2) {
				T temp = arr[n2];
				arr[n2] = arr[n1];
				arr[n1] = temp;
				n1++;
				n2--;
			}
		}
		return n1;}

	/**
	 * Implement merge sort.
	 * 
	 * It should be:
	 *  stable
	 *  
	 * Have a worst case running time of:
	 *  O(n log n)
	 *  
	 * And a best case running time of:
	 *  O(n log n)
	 *  
	 * @param arr
	 * @return
	 */
	public static <T extends Comparable<T>> T[] mergesort(T[] arr) {
		return divide(arr,0,arr.length); }

	private static <T extends Comparable<T>> T[] divide(T[] arr,int first,int n) {
		if (n>1){
			int n1 = n/2;
			int n2 = n-n1;
			arr = divide(arr,first,n1);
			arr = divide(arr,first+n1,n2);
			arr = merge(arr,first,n1,n2);}
		return arr; }

	@SuppressWarnings("unchecked")
	private static <T extends Comparable<T>> T[] merge(T[] arr, int first, int n1, int n2) {

		T[] t = (T[]) new Comparable[n1+n2];

		int i=0,j=0,k=0;
		while (i<n1 && j<n2) {
			if (arr[first+i].compareTo(arr[first+n1+j])<=0){
				t[k] = arr[first+i];
				i++;}
			else {
				t[k] = arr[first+n1+j];
				j++;}
			k++;}
		while (i<n1){
			t[k] = arr[first+i];
			i++; k++;}
		while (j<n2){
			t[k] = arr[first+n1+j];
			j++; k++;}

		for (int p=0; p<n1+n2; p++)
			arr[first+p] = t[p];

		return arr;	}


	/**
	 * Implement radix sort
	 * 
	 * Hint: You can use Integer.toString to get a string
	 * of the digits. Don't forget to account for negative
	 * integers, they will have a '-' at the front of the
	 * string.
	 * 
	 * It should be:
	 *  stable
	 *  
	 * Have a worst case running time of:
	 *  O(kn)
	 *  
	 * And a best case running time of:
	 *  O(kn)
	 * 
	 * @param arr
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public static int[] radixsort(int[] arr) {
		int temp=0,length=0;
		for (int i=0;i<arr.length;i++) {
			String str = Integer.toString(arr[i]);
			if ("-".equals(str.substring(0,1))){  //neg
				temp = str.length()-1;
				if (temp>length)
					length = temp;}
			else{
				temp = str.length();
				if (temp>length)
					length = temp;}
		}

		ArrayList<Integer>[] bucket = new ArrayList[20]; // cap bucket
		for (int i=0;i<bucket.length;i++)
			bucket[i] = new ArrayList<Integer>();
		int track=0,x=0;
		while (track < length) {
			for (int i=0;i<arr.length;i++) {
				int num = arr[i];
				String strD = Integer.toString(num);
				String store = null;
				if (strD.length()-track> 0) {
					store = strD.substring(strD.length()-1-track,strD.length()-track);}
				x=0;
				if (!(store==null || store.equals("-"))) x = Integer.parseInt(store); //change
				if (num<0) x=-x;
				bucket[x+10].add(num);}
			track++;
			int index = 0;
			for (int j=0;j<bucket.length;j++) 
				while (!bucket[j].isEmpty()) {
					int temp2 = bucket[j].get(0);
					bucket[j].remove(0);
					arr[index] = temp2;
					index++; }			
		}
		return arr;
	}

}